package com.lsa.letcode.the46.permutations;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Assert;
import org.junit.Test;

public class PermutationTest {
	@Test
	public void testPermutation() {
		Solution s = new Solution();
		testPermutation(s, new int[] { 1, 2, 4, 3 }, new int[] { 1, 3, 2, 4 });
		testPermutation(s, new int[] { 1, 3, 2, 4 }, new int[] { 1, 3, 4, 2 });
		testPermutation(s, new int[] { 1, 3, 4, 2 }, new int[] { 1, 4, 2, 3 });
		testPermutation(s, new int[] { 1, 4, 2, 3 }, new int[] { 1, 4, 3, 2 });
		testPermutation(s, new int[] { 1, 4, 3, 2 }, new int[] { 2, 1, 3, 4 });

		testPermutation(s, new int[] { 1, 2, 4, 3, 5 }, new int[] { 1, 2, 4, 5,
				3 });
		testPermutation(s, new int[] { 1, 2, 4, 5, 3 }, new int[] { 1, 2, 5, 3,
				4 });
		testPermutation(s, new int[] { 1, 2, 5, 3, 4 }, new int[] { 1, 2, 5, 4,
				3 });
		testPermutation(s, new int[] { 1, 2, 5, 4, 3 }, new int[] { 1, 3, 2, 4,
				5 });

		testPermutation(s, new int[] { 1, 1, 5 }, new int[] { 1, 5, 1 });
		testPermutation(s, new int[] { 1, 5, 1 }, new int[] { 5, 1, 1 });
		testPermutation(s, new int[] { 5, 1, 1 }, new int[] { 1, 1, 5 });

		testPermutation(s, new int[] { 1, 1, 5, 1 }, new int[] { 1, 5, 1, 1 });

		testPermutation(s, new int[] { 1, 2 }, new int[] { 2, 1 });
		testPermutation(s, new int[] { 2, 1 }, new int[] { 1, 2 });

		testPermutation(s, new int[] { 5, 4, 3, 2, 1 }, new int[] { 1, 2, 3, 4,
				5 });

		testPermutations(s, Arrays.asList(Arrays.asList(1, 2, 3),
				Arrays.asList(1, 3, 2), Arrays.asList(2, 1, 3),
				Arrays.asList(2, 3, 1), Arrays.asList(3, 1, 2),
				Arrays.asList(3, 2, 1)), new int[] { 1, 2, 3 });

		testPermutations(s, Arrays.asList(Arrays.asList(1, 2, 2, 3),
				Arrays.asList(1, 2, 3, 2), Arrays.asList(1, 3, 2, 2),
				Arrays.asList(2, 1, 2, 3), Arrays.asList(2, 1, 3, 2),
				Arrays.asList(2, 2, 1, 3), Arrays.asList(2, 2, 3, 1),
				Arrays.asList(2, 3, 1, 2), Arrays.asList(2, 3, 2, 1),
				Arrays.asList(3, 1, 2, 2), Arrays.asList(3, 2, 1, 2),
				Arrays.asList(3, 2, 2, 1)), new int[] { 1, 2, 2, 3 });

		testPermutations(s,
				Arrays.asList(Arrays.asList(1, 2), Arrays.asList(2, 1)),
				new int[] { 1, 2 });
		
		testPermutations(s, Arrays.asList(Arrays.asList(1)), new int[] { 1 });
		testPermutations(s, Arrays.asList((List<Integer>)new ArrayList<Integer>()), new int[] { });
		testPermutations(s, Arrays.asList(Arrays.asList(1, 1, 2),
				Arrays.asList(1, 2, 1), Arrays.asList(2, 1, 1)), new int[] { 1,
				1, 2 });
	}

	private void testPermutations(Solution s, List<List<Integer>> expected,
			int[] input) {
		Assert.assertEquals(expected, s.permute(input));
	}

	private void testPermutation(Solution s, int[] seq, int[] expected) {
		s.nextPermutation(seq);
		Assert.assertArrayEquals(expected, seq);
	}

	@Test
	public void testReverse() {
		Solution s = new Solution();
		{
			int[] seq = { 1, 2, 3, 4 };
			s.reverse(seq);
			Assert.assertArrayEquals(new int[] { 4, 3, 2, 1 }, seq);
		}

		{
			int[] seq = { 1, 2, 3, 4, 5 };
			s.reverse(seq);
			Assert.assertArrayEquals(new int[] { 5, 4, 3, 2, 1 }, seq);
		}

		{
			int[] seq = { 1, 2, 3, 4, 5 };
			s.reverse(seq, 1, 3);
			Assert.assertArrayEquals(new int[] { 1, 4, 3, 2, 5 }, seq);
		}

		{
			int[] seq = { 1, 2, 3, 4, 5 };
			s.reverse(seq, 0, 3);
			Assert.assertArrayEquals(new int[] { 4, 3, 2, 1, 5 }, seq);
		}

		{
			int[] seq = { 1, 2, 3, 4, 5 };
			s.reverse(seq, 1, 4);
			Assert.assertArrayEquals(new int[] { 1, 5, 4, 3, 2 }, seq);
		}
	}
}